from typing import *


class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        sums = [[[0] * 2 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                v = grid[i - 1][j - 1]
                sums[i][j][0] = (
                    sums[i - 1][j][0] + sums[i][j - 1][0] - sums[i - 1][j - 1][0]
                )
                sums[i][j][1] = (
                    sums[i - 1][j][1] + sums[i][j - 1][1] - sums[i - 1][j - 1][1]
                )
                if v == "X":
                    sums[i][j][0] += 1
                elif v == "Y":
                    sums[i][j][1] += 1
                if sums[i][j][0] == sums[i][j][1] and sums[i][j][0] > 0:
                    ans += 1
        return ans


s = Solution()
print(s.numberOfSubmatrices([["X", "Y", "."], ["Y", ".", "."]]))
